package com.xyhuo.leetcode.november;

import java.util.*;

/**
 * 单词拆分
 * https://leetcode.cn/problems/word-break
 *
 * @time 2023/11/24
 */
public class WordBreak {

    public boolean wordBreak(String s, List<String> wordDict) {
        int length = s.length();
        int[] dp = new int[length];
        for (int i = 0; i < length; i++) {
            for (String word : wordDict) {
                int wordLength = word.length();
                if (i - wordLength + 1 < 0) {
                    continue;
                }
                String tmp = s.substring(i - wordLength + 1, i + 1);
                if (tmp.equals(word) && (i - wordLength == -1 || dp[i - wordLength] == 1)) {
                    dp[i] = 1;
                }
            }
        }
        return dp[length - 1] == 1;
    }

//    public static void main(String[] args) {
//        WordBreak wordBreak = new WordBreak();
////        List<String> wordDict = new ArrayList<>();
////        wordDict.add("cats");
////        wordDict.add("dog");
////        wordDict.add("sand");
////        wordDict.add("and");
////        wordDict.add("cat");
//
////        boolean result = wordBreak.wordBreak("catsandog", wordDict);
//
//        List<String> wordDict = new ArrayList<>();
//        wordDict.add("aa");
//        wordDict.add("aaa");
//        wordDict.add("aaaa");
//        wordDict.add("aaaaa");
//        wordDict.add("aaaaaa");
//        wordDict.add("aaaaaaa");
//        wordDict.add("aaaaaaaa");
//        wordDict.add("aaaaaaaaa");
//        wordDict.add("aaaaaaaaaa");
//        boolean result = wordBreak.wordBreak("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", wordDict);
//        System.out.println(result);
//    }
}
